package Day_017_T055;

import java.util.Arrays;

/**
 * 给定一个非负整数数组nums ，你最初位于数组的 第一个下标 。
 *
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 *
 * 判断你是否能够到达最后一个下标。
 *
 *
 *
 * 示例1：
 *
 * 输入：nums = [2,3,1,1,4]
 * 输出：true
 * 解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
 * 示例2：
 *
 * 输入：nums = [3,2,1,0,4]
 * 输出：false
 * 解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 3 * 104
 * 0 <= nums[i] <= 105
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/jump-game
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class T055 {

//解题思路 从后往前遍历 例如 取最后一个数i 判断 在i-1的范围内有没有能达到最后一个数 的  如果有 就截掉他 让前一个数成为最后一个数
    //如果没找到 说明 永远也达不到最后一个数

    public boolean canJump(int[] nums) {

        if (nums.length == 0) {
            return true;
        }

        //获取最后一个数
//        int lastNum = nums[nums.length - 1];
//        System.out.println("lastName:"+lastNum);
//
//        //从前往后遍历 数组 一直到倒数第二个数
//        for (int i = 0;i<nums.length-1; i++) {
//
//            if (nums[i] >=nums.length-1-i) {  //如果出现 i下标位置上的数 大于等于 他到最后一个数的距离 就进行截取
//
//                int[] newData = Arrays.copyOfRange(nums, 0, i+1);
//                for (int newDatum : newData) {
//                    System.out.print(newDatum+" ");
//                }
//
//                canJump(newData);
//                break;
//            }
//
//        }

        //index作为 最后一个数 的下标
        int index = nums.length-1;

        for (int i = index-1; i >=0 ; i--) {
            //当前数字的值 大于或者等于两者坐标的距离 就可以达到
            if (nums[i]>=index-i){

                index = i;   //如果能达到 就 将i的位置作为最后一个数

            }

        }

        return index==0;  //如果循环完毕 后 index的下标不是0 说明index 所在的下标 没有数能够达到

    }

    public static void main(String[] args) {
        T055 t055 = new T055();

        boolean b = t055.canJump(new int[]{2, 3, 1, 1, 4});
        System.out.println(b);
    }

}
